package pers.qianyu.month_202012.date_20201214;

import org.junit.*;

import java.util.*;

/**
 * 91. 解码方法
 * https://leetcode-cn.com/problems/decode-ways/description/
 *
 * @author mizzle rain
 * @date 2020-12-14 14:19
 */
public class NumDecodings {
    public int numDecodings(String s) {
        if (s.length() == 0 || s.charAt(0) == '0') {
            return 0;
        }
        int len = s.length();
        if (len < 2) {
            return len;
        }
        char[] arr = s.toCharArray();
        int count = 0;
        // 如果连续两个 0 出现，一定不可编码
        for (int i = 0; i < len; i++) {
            if (arr[i] == '0') {
                count++;
                if (count > 1) {
                    return 0;
                }
            } else {
                count = 0;
            }
        }
        // dp[i] 表示 前 i 个字符的解码方式
        int[] dp = new int[len + 1];
        dp[0] = 1;
        dp[1] = s.charAt(0) == '0' ? 0 : 1;
        for (int i = 2; i < len + 1; i++) {
            int num = (arr[i - 2] - '0') * 10 + (arr[i - 1] - '0');
            if (num <= 26 && num >= 10) {
                if (num == 10 || num == 20) {
                    dp[i] = dp[i - 2];
                } else {
                    dp[i] = dp[i - 1] + dp[i - 2];
                }
            } else {
                if (arr[i - 1] == '0') {
                    return 0;
                }
                dp[i] = dp[i - 1];
            }
        }
        System.out.println(Arrays.toString(dp));
        return dp[len];
    }

    @Test
    public void test1() {
        int result = new NumDecodings().numDecodings("226");
        System.out.println("result = " + result);
    }

    @Test
    public void test2() {
        int result = new NumDecodings().numDecodings("10");
        System.out.println("result = " + result);
    }

    @Test
    public void test3() {
        int result = new NumDecodings().numDecodings("2101");
        System.out.println("result = " + result);
    }
}
